// 大数相加
const bigAdd = (a, b) => {
    const maxLen = Math.max(a.length, b.length);
    a = a.padStart(maxLen, 0);
    b = b.padStart(maxLen, 0);

    let cur = 0;
    let curry = 0;
    let sum = "";

    for(let i = maxLen - 1; i > 0;i--){
        cur = a[i] + b[i] + curry;
        curry = Math.floor(cur / 10);
        sum = cur + sum;
    }
    
    if(curry === 1) {
        sum = "1" + sum;
    }

    return sum;
}

// 带并发限制的fetch
function sendRequest(urls, max, callback){
    let pending_count = 0;
    let idx = 0;

    while(pending_count < max)
        _fetch(ulrs[idx++]);

    async function _fetch(url){
        if(!url) return;
        pending_count++;
        await fetch(url);
        pending_count--;
        _fetch(urls[idx++]);
        pending_count || callback && callback();
    }
}

let urls = Array.from({length: 10}, (_, index) => index);

// 二分查找
function binary_search(low, high, key, arr) {
    if(low > high) return -1;
    let mid = Math.floor((low + high) / 2);

    if(arr[mid] === key)
        return mid;
    else if (arr[mid] > key) {
        high = mid - 1;
        return binary_search(low, high, key, arr);
    } else if (arr[mid] < key) {
        low = mid + 1;
        return binary_search(low, high, key, arr);
    }
}

// 发布订阅模式
function Subject() {
    this.observers = [];
}

Subject.prototype = {
    subscribe: function(observer, options) {
        const {once ,priority} = options;
        this.observers.push({observer, once, priority});
        this.observers.sort((a, b) => b.priority - a.priority);
    },

    unsubscribe: function(observerToRemove) {
        this.observers = this.observers.filter(observer => 
            observer.observer !== observerToRemove
        )
    },

    publish: function(data) {
        const current = [...this.observers];
        current.forEach(observer => {
            observer.observer(data);
            
            if(observer.once)
                this.unsubscribe(observer);
        })
    }
}


// 反转列表
const reverseList = (head) => {
    let pre = null;
    let cur = head;
    let next = head;

    while(cur) {
        next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }

    return cur;
}


// 防抖:事件在N秒后执行回调，如果在N秒内又被触发，会重新计时。
function debounce(fn, wait) {
    var timer = null;
    return function(...args){
        if(timer)
            clearTimeout(timer)
        else 
            timer = setTimeout(() => {
                fn.apply(this,args);
                timer = null;
        },wait)
    }
}

// 节流: 事件在触发N秒后执行回调，N秒内触发无效
function throttle(fn, wait) {
    var timer = null;
    return function(...args) {
        if(!timer) {
            timer = setTimeout(() => {
                fn.apply(this, args);
                timer = null;
            }, wait)
        }
    }
}

function throttle1(fn, wait) {
    var prev = new Date();
    return function(...args){
        var now = new Date();
        if(now - prev >= wait){
            fn.apply(this, args);
            prev = new Date();
        }
    }
}

// 归并排序
const merge = (left, right) => {
    const result = [];
    let i = 0, j = 0;
    while(i < left.length && j < right.length) {
        if(left[i] < right[j]) {
            result.push(left[i++]);
        }else {
            result.push(right[j++]);
        }
    }
    return result.concat(left[i].slice()).concat(right[j].slice()); 
}

const mergeSort = (arr) => {
    if(arr.length <= 1)
        return arr;

    let mid = Math.floor(arr.length / 2);
    let left = arr.slice(0, mid);
    let right = arr.slice(mid);

    return merge(mergeSort(left), mergeSort(right));
}


// 函数柯利化
function curry(fn,...args) {
    return fn.length === args.length ? fn(...args) :
        curry.bind(null, fn, ...args);
}

    // 动态传入参数个数
function dynamicCurry(fn) {
    const args = [];
    
    function curried(...newArgs) {
        args.push(...newArgs);
        return curried;
    }

    curried.end = function() {
        return fn(...args);
    }

    return curried;
}


// 将数组转为树形结构
var menu_list = [{
    id: '1',
    menu_name: '设置',
    menu_url: 'setting',
    parent_id: 0
   }, {
    id: '1-1',
    menu_name: '权限设置',
    menu_url: 'setting.permission',
    parent_id: '1'
   }, {
    id: '1-1-1',
    menu_name: '用户管理列表',
    menu_url: 'setting.permission.user_list',
    parent_id: '1-1'
   }, {
    id: '1-1-2',
    menu_name: '用户管理新增',
    menu_url: 'setting.permission.user_add',
    parent_id: '1-1'
   }, {
    id: '1-1-3',
    menu_name: '角色管理列表',
    menu_url: 'setting.permission.role_list',
    parent_id: '1-1'
   }, {
    id: '1-2',
    menu_name: '菜单设置',
    menu_url: 'setting.menu',
    parent_id: '1'
   }, {
    id: '1-2-1',
    menu_name: '菜单列表',
    menu_url: 'setting.menu.menu_list',
    parent_id: '1-2'
   }, {
    id: '1-2-2',
    menu_name: '菜单添加',
    menu_url: 'setting.menu.menu_add',
    parent_id: '1-2'
   }, {
    id: '2',
    menu_name: '订单',
    menu_url: 'order',
    parent_id: 0
   }, {
    id: '2-1',
    menu_name: '报单审核',
    menu_url: 'order.orderreview',
    parent_id: '2'
   }, {
    id: '2-2',
    menu_name: '退款管理',
    menu_url: 'order.refundmanagement',
    parent_id: '2'
   }
]

const buildTree = (arr) => {
    const result = {};
    const temp = {};

    for(let i = 0; i < arr.length; i++) {
        temp[arr[i].id] = arr[i]
    }

    for(let i = 0; i < temp.length; i++) {
        if(temp[i].parent_id) {
            if(!temp[temp[i].parent_id].children)
                temp[temp[i].parent_id].children = new Object();
            temp[temp[i].parent_id].children[temp[i].id] = temp[i];
        }else {
            result[temp[i].id] = temp[temp[i].id];
        }
    }
}

// 将http header转换为JS对象
/**
 * --- 测试用例 ---
 * 
 * 输入：
 * `Accept-Ranges: bytes 
 * Cache-Control: max-age=6000, public
 * Connection: keep-alive
 * Content-Type: application/javascript`
 * 
 * 输出：
 * {
 *   "Accept-Ranges": "bytes",
 *   "Cache-Control": "max-age=6000, public",
 *   Connection: "keep-alive",
 *   "Content-Type": "application/javascript"
 * }
 */
const solution = (s) => {
    const result = {};
    const arr = s.split('\n');

    arr.forEach(item => {
        const temp = item.split(":");
        result[temp[0]] = temp[1] 
    })
    
    return result;
}


// 快速排序
function quickSort(start, end, arr) {

}

// 冒泡排序
function bubbleSort(arr) {
    for(let i = 0; i < arr.length - 1; i++) {
        for(let j = 0;j < arr.length - i - 1; j++) {
            if(arr[j] > arr[j+1])
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
        }
    }
    return arr;
}

// 判断是否是回文数
function is(s) {
    return s.toString().split('').reverse().join('') === s.toString();
}   

// 求出一个集合所有的子集
function subSets(index, nums) {
    const result = [];
    
    function dfs(index, path) {
        result.push(path.slice());
        for(let i = index; i < nums.length; i++) {
            path.push(nums[i])
            dfs(index++, path);
            path.pop();
        }
    }

    dfs(0, []);
    return result;
}

// 全排列
function permute(nums) {
    const result = [];
    const used = {};

    function dfs(path) {
        if(path.length === nums.length){
            result.push(path.slice());
            return;
        }

        for(let num of nums) {
            if(used) continue;
            used[num] = true;
            path.push(num);
            dfs(path);
            used[num] = false;
            path.pop();
        }
    }
    dfs([]);
    return result;
}

// 深拷贝
function deepCopy(obj) {
    if(typeof obj !== 'object' || obj === null)
        return obj;
    const result = obj instanceof Array ? [] : {};
    for (let key in obj)
        if(obj.hasOwnProperty(key))
            result[i] = deepCopy(obj[key]);
    return result;
}

// 实现千位分隔符
function numFormat(num) {
    num = num.toString().split('.');
    const result = [];
    const arr = num[0].split('').reverse();
    for(let i = 0; i < arr.length; i++) {
        if(i % 3 === 0 && i !== 0)
            result.push(',');
        result.push(arr[i]);
    }
    if(arr[1])
        result = result.reverse().join('').concat('.' + arr[1]);
    else
        result = result.reverse().join('');
    
    return result;
}

// 实现字符串翻转
function reverse(s) {
    if(s.length <=1)
        return s;
    return reverse(s.slice(1)) + s[0];
}

// 实现trim方法
function myTrim(s) {
    const reg = /^\s+|\s+$/g;
    return s.replace(reg,"");
}

// 实现 setTimeout模拟setInterval
function mySetInterval(fn, wait) {
    let res = {target:''};

    function test(){
        fn();
        res.target = setTimeout(test, wait);
    }
    test();
    return res;
}

function myClearInterval(timer) {
    clearTimeout(timer.target);
}

// 手写寄生组合继承
function Parent(name) {
    this.name = name;
    this.say = () => {
        console.log(111);
    }
}

Parent.prototype.play = () => {
    console.log(222);
}

function Children(name, age){
    Parent.call(this, name);
    this.age = age;
}

Children.prototype = Object.create(Parent.prototype);
Children.prototype.constructor = Children;

let c = new Children('Tom', 18);
console.log(c.constructor === Children)
console.log(c.play());

// 手写解析url
/**
 * --- 题目描述 ---
 * 
 * 实现一个函数，可以对 url 中的 query 部分做拆解，返回一个 key: value 形式的 object  
 * 
 * --- 实例 ---
 * 
 * 输入：'http://sample.com/?a=1&e&b=2&c=xx&d#hash' 
 * 输出：{a: 1, b: 2, c: 'xx', d: ''}  
 */
function getQueryObj(url){
    let queryObj = {};
    urlObj = new URL(url);
    urlObj.search.slice(1,urlObj.search.length)
    .split('&').forEach(item => {
        let arr = item.split('=');
        queryObj[arr[0]] = arr[1] || '';
    })
    return queryObj;
}

/**
 * --- 题目描述 ---
 *
 * 实现一个 parseParam 函数，将 url 转化为指定结果
 *
 * --- 测试用例 ---
 *
 * 输入：url = 'http://www.domain.com/?user=anonymous&id=123&id=456&city=%E5%8C%97%E4%BA%AC&enabled'
 * 输出：
{
 user:'anonymous',
 id:[123,456],// 重复出现的 key 要组装成数组，能被转成数字的就转成数字类型
 city:'北京',// 中文需解码
 enabled: true // 未指定值的 key 与约定为 true
}
*/
const parseParam = (url) => {
    const queryObj = {};
    const arr = url.split('?')[1].split('&');
    arr.forEach(item => {
        const temp = item.split('=');
        val = temp[1] !== '' && !isNaN(temp[1]) ? Number(temp[1]) : temp[1];
        if(queryObj[temp[0]])
            if(Array.isArray(queryObj[temp[0]]))
                queryObj[temp[0]].push(val)
            else
                queryObj[temp[0]] = [queryObj[temp[0]]].concat(val);
        else
            if(val)
                queryObj[temp[0]] = decodeURI(val);
            else
                queryObj[temp[0]] = true;
    })
    return queryObj;
}
console.log(parseParam('http://www.domain.com/?user=anonymous&id=123&id=456&city=%E5%8C%97%E4%BA%AC&enabled'));

// 手写AJAX请求
const xhr = new XMLHttpRequest();
xhr.open('GET', 'http://www.example.com');
xhr.send();
xhr.onreadystatechange = () => {
    if(xhr.readyState === 4) {
        if(xhr.status >= 200 && xhr.status < 300)
            console.log(xhr.responseText);
        else 
            console.log('请求失败');
    }
}

// Promise封装AJAX
const p = new Promise((resolve, reject) => {
    const xhr = new XMLHttpRequest();
    xhr.open('GET', 'http://www.example.com');
    xhr.send();
    xhr.onreadystatechange = () => {
        if(xhr.readystate === 4){
            if(xhr.status >= 200 && xhr.status < 300)
                resolve(xhr.responseText);
            else
                reject(xhr.status);
        }
    }
})


// LRU缓存
const LRU = class {
    constructor(capacity) {
        this.cache = new Map();
        this.capacity = capacity;
    }

    get(key) {
        let cache = this.cache;
        if(cache.has(key)){
            let temp = cache.get(key);
            cache.delete(key);
            cache.set(key, temp);
            return temp;
        }else {
            return -1;
        }
    }

    put(key, value){
        let cache = this.cache;
        if(cache.has(key)){
            cache.delete(key)
        }else if(cache.size >= this.capacity) {
            cache.delete(cache.keys().next().value);
        }
        cache.set(key, value);
    }
}

// 手写apply
function myApply(context) {
    if(typeof this !== "function")
        throw new TypeError('Error');
    context = context || window;
    context.fn = this;
    const result = arguments[1] ? context.fn(...arguments[1]) : context.fn();
    delete context.fn;
    return result;
}

// 手写call
function myCall(context) {
    if(typeof this !== 'function')
        throw new TypeError('Error');
    context = context || window;
    context.fn = this;
    const args = [...arguments].slice(1);
    const result = context.fn(...args);
    delete context.fn;
    return result;
}

// 手写bind
function myBind(context) {
    if(typeof this !== 'function')
        throw new TypeError('Error');
    context = context || window;
    context.fn = this;
    const args = [...arguments].slice(1);
    return function Fn() {
        const result = context.fn.apply(this instanceof Fn ? this : context, args.concat(...arguments))
        delete context.fn;
        return result;
    }
}

// 手写instanceof
function myInstanceof(leftValue, rightValue) {
    if(typeof rightValue !== "function")
        throw new TypeError();
    leftValue = leftValue.__proto__;
    while(leftValue) {
        if(leftValue === rightValue.prototype)
            return true;
        leftValue = leftValue.__proto__;
    }
    return false;
}

// 手写new操作符
function myNew() {
    const obj = {};
    const Constructor = [].shift().apply(arguments);
    obj.__proto__ = Constructor.prototype;
    const ret = Constructor.apply(obj, [...arguments]);
    return typeof ret === 'object' && ret!== null ? ret : obj; 
}

// 手写Promise.all
const myPromiseAll = (promises) => {
    return new Promise((resolve, reject) => {
        if(!Array.isArray(promises))
            return reject(new TypeError('arguments must be an array'));
        var resolvedCounter = 0;
        var resolvedValues = new Array(promises.length);
        for(let i = 0;i < promises.length; i++){
            Promise.resolve(promises[i]).then(
                value => {
                    resolvedCounter++;
                    resolvedValues[i] = value;
                    if(resolvedCounter === promises.length)
                        return resolve(resolvedValues);
                },
                reason => {
                    return reject(reason);
                }
            )
        }
    })
}

// 手写Promise
const PENDING = 'pending';
const FULFILLED = 'fulfilled';
const REJECTED = 'rejected';

function Promise(executor) {
    let self = this;
    this.status = PENDING;
    self.onFulfilled = [];
    self.onRejected = [];

    function resolve(value) {
        if(self.status === PENDING) {
            self.status = FULFILLED;
            self.value = value;
            queueMicrotask(() => self.onFulfilled.forEach(fn => fn()));
        }
    }

    function reject(reason) {
        if(self.status === PENDING) {
            self.status = REJECTED;
            self.reason = reason;
            queueMicrotask(() => self.onRejected.forEach(fn => fn()));
        }
    }

    try {
        executor(resolve, reject);
    }catch(e){
        reject(e);
    }
}

Promise.prototype.then = function(onFulfilled, onRejected) {
    onFulfilled = typeof onFulfilled === 'function' ? onFulfilled : value => value;
    onRejected = typeof onRejected === 'function' ? onRejected : reason => {throw reason};

    let self = this;
    let promise2 = new Promise((resolve, reject) => {
        if(self.status === FULFILLED) {
            queueMicrotask(() => {
                try {
                    let x = onFulfilled(self.value);
                    resolvePromise(promise2, x, resolve, reject);
                }catch (e){
                    reject(e);
                }
            })
        } else if (self.status === REJECTED){
            queueMicrotask(() => {
                try{
                    let x = onRejected(self.reason);
                    resolvePromise(promise2, x, resolve, reject);
                }catch (e) {
                    reject(e);
                }
            })
        } else if (self.status === PENDING) {
            self.onFulfilled.push(() => {
                queueMicrotask(() => {
                    try {
                        let x = onFulfilled(self.value);
                        resolvePromise(promise2, x, resolve, reject);
                    } catch(e) {
                        reject(e);
                    }
                })
            })

            self.onRejected.push(() => {
                queueMicrotask(() => {
                    try {
                        let x = onRejected(self.value);
                        resolvePromise(promise2, x, resolve, reject)
                    } catch(e) {
                        reject(e);
                    }
                })
            })
        }
    })
    return promise2;
}

function resolvePromise(promise, x, resolve, reject) {
    if (promise === x) {
        reject(new TypeError('Chaining cycle'));
    }
    if ((x && typeof x === 'object') || typeof x === 'function') {
        let used;
        try {
            let then = x.then;
            if (typeof then === 'function') {
                then.call(  
                    x,
                    y => {
                        if (used) return;
                        used = true;
                        resolvePromise(promise, y, resolve, reject);
                    },
                    r => {
                        if(used) return;
                        used = true;
                        reject(r);
                    }
                )
            } else {
                if(used) return;
                used = true;
                resolve(x);
            }
        } catch(e){
            if(used) return;
            used = true;
            reject(e);
        }
    } else {
        resolve(x);
    }
}
Promise.defer = function() {
    let result = {};
    result.promise = new Promise((resolve, reject) => {
        result.resolve = resolve;
        result.reject = reject;
    })
    return result;
}

// 手写Promise.race
Promise.myRace = function(promises) {
    return new Promise((resolve, reject) => {
        if(!Array.isArray(promises))
            return reject(new TypeError('arguments must be an array'))
        for (let i = 0; i < promises.length; i++){
            Promise.resolve(p).then(
                value => {
                    return resolve(value);
                },
                reason => {
                    return reject(reason);
                }
            )
        }
    })
}

// 手写map
function myMap(arr, mapCallback) {
    if(!Array.isArray(arr) || arr.length === 0 || typeof mapCallback !== 'function')
        return [];
    else {
        let result = [];
        for(let i = 0; i < result.length; i++){
            result.push(mapCallback(result[i], i, arr));
        }
        return result;
    }
};

// 手写reduce
function myReduce(arr, reduceCallback, initialValue) {
    if(!Array.isArray(arr) || arr.length === 0 || typeof reduceCallback !== "function")
        return [];
    else {
        let value = initialValue ? initialValue : arr[0];
        for(let i = initialValue ? 0 : 1;i < arr.length; i++) {
            value = reduceCallback(value, arr[i], i, arr)
        }
        return value;
    }
}

// 手写filter
function filter(arr, filterCallback) {
    if(!Array.isArray(arr) || arr.length === 0 || typeof filterCallback !== 'function')
        return [];
    else {
        let result = [];
        for(let i = 0; i< arr.length; i++){
            if(!filterCallback(arr[i], i, arr)){
                result.push(arr[i]);              r
            }
        }
        return result;
    }
}

// 找出不含有重复字符的最长子串长度
const lengthOfLongestSubstring = (s) => {
    let window = {};
    let left = 0;
    let right = 0;
    let maxLen = 0;
    while(right < s.length) {
        let current = s[right];
        window[current] ? window[current]++ : window[current] = 1;
        right ++;
        while(window[current] > 1) {
            let now = s[left];
            left++;
            window[now]--;
        }
        maxLen = Math.max(maxLen, right-left);
    }
    return maxLen;
}

// 数组去重
const arr = [1,2,2,3,3,4,5,5,6];
console.log(new Set(arr));
console.log(arr.filter((item, index) => arr.indexOf(item) === index))
console.log(arr.reduce((prev, cur) => prev.includes(cur) ? prev : [...prev, cur], []))

function noRepeat(arr) {
    for(let i = 0; i < arr.length; i++){
        if(arr.indexOf(arr[i] !== i)) {
            arr.splice(i, 1);
            i--;
        }
    }
    return arr;
}

// 数组扁平化
const flat1 = (arr) => {
    const result = [];
    arr.forEach(item => {
        if(Array.isArray(item))
            result = result.concat(flat1(item));
        else 
            result.push(item);
    })
    return result;
}

const flat2 = (arr) => {    
    return arr.reduce((prev, cur) => {
        if(Array.isArray(cur))
            return prev.concat(flat2(cur));
        else
            return prev.concat(cur);
    }, [])
}

const flat3 = (arr) => {
    const result = [];
    const stack = arr.slice();
    while(stack.length !== 0) {
        let val = stack.pop();
        if(Array.isArray(val)) {
            stack.push(...val);
        }else{
            result.unshift(val);
        }
    }
}
